package com.study.algorithm.datastruct.tree.impl;

import com.study.algorithm.datastruct.tree.TreeTravel;
import com.study.algorithm.datastruct.tree.model.Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 树遍历实现（针对多叉树）
 * 实现：层次遍历
 */

public class TreeTravelImpl implements TreeTravel<Tree> {

    @Override
    public List<Tree> getLevelTravelTrace(Tree tree) {
        List<Tree> traceList = new ArrayList<>();
        Queue<Tree> treeQueue = new LinkedBlockingQueue<>();
        if (tree == null) {
            return traceList;
        }
        treeQueue.add(tree);
        levelTravel(traceList, treeQueue);
        return traceList;
    }

    private void levelTravel(List<Tree> traceList, Queue<Tree> treeQueue) {
        while (!treeQueue.isEmpty()) {
            Tree tree = treeQueue.poll();
            if (tree == null) {
                continue;
            }
            traceList.add(tree);
            if (tree.hasChildNode()) {
                List<Tree> treeNodes = tree.getChildrenNode();
                for (Tree treeNode : treeNodes) {
                    treeQueue.add(treeNode);
                }
            }
        }
    }

}
